/*
 * @lc app=leetcode.cn id=2044 lang=cpp
 *
 * [2044] 统计按位或能得到最大值的子集数目
 */

// @lc code=start
class Solution
{
    int n;

public:
    void dfs(vector<int> &nums, int idx, int orVal, int &ans, int &maxOrVal)
    {
        if (idx == n)
        {
            if (orVal > maxOrVal)
            {
                maxOrVal = orVal;
                ans = 1;
            }
            else if (orVal == maxOrVal)
            {
                ans++;
            }
            return;
        }
        dfs(nums, idx + 1, orVal | nums[idx], ans, maxOrVal);
        dfs(nums, idx + 1, orVal, ans, maxOrVal);
    };
    int countMaxOrSubsets(vector<int> &nums)
    {
        int ans = 0, maxOrVal = 0;
        n = nums.size();
        dfs(nums, 0, 0, ans, maxOrVal);
        return ans;
    }
};
// @lc code=end
